package search;

/**
 * 二分查找 折半法
 * <p>
 * 说明：元素必须是有序的，如果是无序的则要先进行排序操作。
 */
public class BinarySearch {

    /**
     * 查找 =key 的，没有返回-1
     */
    public static int bs1(int[] array, int key) {
        int L = 0, R = array.length - 1;
        int mid;
        while (L <= R) {
            mid = L + (R - L) / 2;
            if (key < array[mid]) {
                R = mid - 1;
            } else if (key > array[mid]) {
                L = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 第一个`=key`的，不存在返回`-1`
     */
    public static int bs2(int[] array, int key) {
        int L = 0, R = array.length - 1;
        int mid;
        while (L <= R) {
            mid = L + (R - L) / 2;
            if (array[mid] >= key) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        if (L < array.length && array[L] == key) {
            return L;
        }
        return -1;
    }

    /**
     * 第一个`>=key`的
     */
    public static int bs3(int[] array, int key) {
        int L = 0, R = array.length - 1;
        int mid;
        while (L <= R) {
            mid = L + (R - L) / 2;
            if (array[mid] >= key) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return L;
    }

    /**
     * 第一个`>key`的
     */
    public static int bs4(int[] array, int key) {
        int L = 0, R = array.length - 1;
        int mid;
        while (L <= R) {
            mid = L + (R - L) / 2;
            if (array[mid] > key) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return L;
    }

    /**
     * 最后一个`=`key的，不存在返回`-1`
     */
    public static int bs5(int[] array, int key) {
        int L = 0, R = array.length - 1;
        int mid;
        while (L <= R) {
            mid = L + (R - L) / 2;
            if (array[mid] <= key) {
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        if (R >= 0 && array[R] == key) {
            return R;
        }
        return -1;
    }

    /**
     * 最后一个`<=key`的
     */
    public static int bs6(int[] array, int key) {

        int L = 0, R = array.length - 1;
        int mid;
        while (L <= R) {
            mid = L + (R - L) / 2;
            if (array[mid] <= key) {
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return R;
    }

    /**
     * 最后一个`<key` 的
     */
    public static int bs7(int[] array, int key) {
        int L = 0, R = array.length - 1;
        int mid;
        while (L <= R) {
            mid = L + (R - L) / 2;
            if (array[mid] < key) {
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return R;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] array = new int[]{3, 12, 32, 41, 41, 41, 52, 65, 76, 83, 92, 100};
        System.out.println(bs7(array, 41));
    }
}
